#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};


class Solution {
public:
    ListNode* rotary(ListNode* phead)
    {
        ListNode* prev = nullptr;
        ListNode* cur = phead;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        head1 = rotary(head1);
        head2 = rotary(head2);
        int i = 0;
        ListNode* cur1 = head1;
        ListNode* cur2 = head2;
        ListNode* phead = nullptr;
        ListNode* cur = nullptr;
        while (cur1 && cur2)
        {
            int p = cur1->val + cur2->val + i;
            ListNode* newnode = new ListNode(p % 10);
            i = p / 10;
            if (phead == nullptr)
            {
                phead = cur = newnode;
            }
            else
            {
                cur->next = newnode;
                cur = cur->next;
            }
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        while (cur1)
        {
            int p = cur1->val + i;
            ListNode* newnode = new ListNode(p % 10);
            i = p / 10;
            if (phead == nullptr)
            {
                phead = cur = newnode;
            }
            else
            {
                cur->next = newnode;
                cur = cur->next;
            }
            cur1 = cur1->next;
        }
        while (cur2)
        {
            int p = cur2->val + i;
            ListNode* newnode = new ListNode(p % 10);
            i = p / 10;
            if (phead == nullptr)
            {
                phead = cur = newnode;
            }
            else
            {
                cur->next = newnode;
                cur = cur->next;
            }
            cur2 = cur2->next;
        }
        if (i)
        {
            cur->next = new ListNode(i);
        }
        phead = rotary(phead);
        return phead;
    }
};


class Solution {
public:
    bool isPail(ListNode* head) {
        // write code here
        ListNode* phead = nullptr;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur)
        {
            phead = new ListNode(cur->val);
            phead->next = prev;
            prev = phead;
            cur = cur->next;
        }
        ListNode* node1 = head;
        ListNode* node2 = phead;
        while (node1 && node2)
        {
            if (node1->val != node2->val)
            {
                return false;
            }
            node1 = node1->next;
            node2 = node2->next;
        }
        return true;
    }
};


class Solution {
public:
    void curing(ListNode*& cur, vector<ListNode*> ptr)
    {
        for (auto l : ptr)
        {
            cur->next = l;
            cur = cur->next;
        }
    }

    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if (head == nullptr)
        {
            return nullptr;;
        }
        vector<ListNode*> one;
        vector<ListNode*> two;
        ListNode* cur = head;
        ListNode* phead = nullptr;
        int i = 1;
        while (cur)
        {
            if (phead == nullptr)
            {
                phead = cur;
            }
            if (i % 2 == 0)
            {
                two.push_back(cur);
            }
            else
            {
                one.push_back(cur);
            }
            i++;
            cur = cur->next;
        }
        cur = phead;
        curing(cur, one);
        curing(cur, two);
        if (cur)
        {
            cur->next = nullptr;
        }
        return phead;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if (head == nullptr)
        {
            return head;
        }
        ListNode* prev = head;
        ListNode* cur = head->next;
        while (cur)
        {
            if (cur->val == prev->val)
            {
                prev->next = cur->next;
                delete cur;
                cur = prev;
            }
            prev = cur;
            cur = cur->next;
        }
        return head;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if (head == nullptr)
        {
            return head;
        }
        unordered_map<int, int> hash;
        ListNode* cur = head;
        while (cur)
        {
            hash[cur->val]++;
            cur = cur->next;
        }
        cur = head;
        ListNode* prev = cur;
        while (cur)
        {
            if (hash[cur->val] > 1)
            {
                ListNode* next = cur->next;
                if (cur == head)
                {
                    head = prev = next;
                }
                else
                {
                    prev->next = next;
                }
                delete cur;
                cur = next;
            }
            else
            {
                prev = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};